/*
 * @lc app=leetcode.cn id=149 lang=cpp
 *
 * [149] 直线上最多的点数
 *
 * https://leetcode-cn.com/problems/max-points-on-a-line/description/
 *
 * algorithms
 * Hard (35.95%)
 * Likes:    397
 * Dislikes: 0
 * Total Accepted:    57K
 * Total Submissions: 157.7K
 * Testcase Example:  '[[1,1],[2,2],[3,3]]'
 *
 * 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：points = [[1,1],[2,2],[3,3]]
 * 输出：3
 *
 *
 * 示例 2：
 *
 *
 * 输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
 * 输出：4
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1
 * points[i].length == 2
 * -10^4 i, yi
 * points 中的所有点 互不相同
 *
 *
 */

// @lc code=start
#include <unordered_map>
#include <vector>
#include <iostream>
#include <climits>
using namespace std;
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        // 分别存储斜率、个数
        unordered_map<double,int> hash;
        int max_count=0,same_y=1;
        for(int i=0;i<points.size();++i){
            same_y=1;
            // 点i和点i之前的元素确定的直线已经计算过，不需要重复算，因此考虑i之后的元素与之配合即可
            for(int j=i+1;j<points.size();++j){
                // 两点斜率为0
                if(points[i][1]==points[j][1]){
                    ++same_y;
                }else{
                    double dx=points[i][0]-points[j][0];
                    double dy=points[i][1]-points[j][1];
                    ++hash[dx/dy];
                }
            }
            max_count=max(max_count,same_y);
            for(auto item:hash){
                max_count=max(max_count,1+item.second);
            }
            hash.clear();
        }
        return max_count;
    }
};
/* struct pairhash {
public:
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const
  {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
}; */

/* class Solution
{
public:
    int maxPoints(vector<vector<int>> &points)
    {
        // 分别存储斜率、个数
        unordered_map<pair<double, double>, int,pairhash> hash;
        int max_count = 0, same_y = 1;
        double k, b;
        for (int i = 0; i < points.size(); ++i)
        {
            // 点i和点i之前的元素确定的直线已经计算过，不需要重复算，因此考虑i之后的元素与之配合即可
            for (int j = i + 1; j < points.size(); ++j)
            {
                // 斜率不存在
                if (points[i][0] == points[j][0])
                {
                    k = INT_MAX;
                    b = INT_MAX;
                }
                else
                {
                    int x1 = points[i][0];
                    int y1 = points[i][1];
                    int x2 = points[j][0];
                    int y2 = points[j][1];
                    double dx = points[i][0] - points[j][0];
                    double dy = points[i][1] - points[j][1];
                    k = dy / dx;
                    b = (x1 * y2 - x2 * y1) / (x1 - x2);
                }
                ++hash[make_pair(k, b)];
            }
        }
        for (auto item : hash)
        {
            cout<<item.first.first<<" "<<item.first.second<<" "<<item.second<<
            max_count = max(max_count,  item.second);
        }
        return max_count;
    }
}; */




// @lc code=end
